//爬楼梯 一个青蛙一次可以爬的台阶范围是[1, n] (n等于楼梯的阶数)。问：爬到楼顶有多少种爬法？
int climbStairs(vector<int> v)
{
	if (v.empty()) {
		return 0;
	}
	int size = v.size();
	vector<int> res(size);
	res[0] = 1;
	if (size < 2) {
		return res[size-1];
	}
	res[1] = 2;
	//前缀和数组
	vector<int> sum(size);
	sum[0] = res[0];
	sum[1] = sum[0] + res[1];
	for (int i = 2;i < size;++i)
	{
		res[i] = sum[i - 1] + 1;
		sum[i] = sum[i - 1] + res[i];
	}
	return res[size - 1];
}